1. Field of the Invention
The present invention relates to content addressable memory (CAM) systems. More specifically, the present invention relates to methods and structures for performing a longest match operation in a CAM system.
2. Discussion of Related Art
CAM cells are defined as memory cells that are referenced in response to their content, rather than by a physical address in an array. FIG. 1 shows a block diagram of a conventional CAM array 100 including twelve CAM cells, three match lines ML0-ML2, four data lines DL0-DL3, four complementary data lines DL0#-DL3#, and a splitter 110. A CAM array is specified by a depth, equal to its number of rows, and a width, equal to its number of columns that define the number and length, respectively, of words that can be stored in the array. For example, CAM array 100 has a depth of three bits (three rows) and a width of four bits (four columns) and is therefore a 3xc3x974 array capable of storing three words of four bits each.
The individual CAM cells in CAM array 100 are labeled Cx,y, where X is the row of the array and Y is the column of the array. Thus, CAM array 100 includes CAM cells C0,0 to C2,3. Each row of CAM cells is coupled to a common match line, and each column of CAM cells is coupled to a common data line and a common complementary data line. For example, CAM cells C0,0, C0,1, C0,2, and C0,3 are all coupled to match line ML0. Similarly, CAM cells C0,0, C1,0, and C2,0 are all coupled to data line DL0 and complementary data line DL0#. In the described example, the data bit value stored in each CAM cell is indicated by either a xe2x80x9c0xe2x80x9d or a xe2x80x9c1xe2x80x9d in brackets. For example, CAM cells C0,0, C0,1, C0,2, and C0,3 store data bit values of 0, 1, 0, and 0, respectively.
The CAM array 100 is addressed by providing a data bit value to each column of stored bit values, or bit slice, in the array. Splitter 110 receives an input word as a four-bit input data value ID[3:0], and applies the individual data bit values ID[0], ID[1], ID[2]and ID[3] to data lines DL0, DL1, DL2, and DL3, respectively. Splitter 110 also provides complementary data bit values ID#[0], ID#[1], ID#[2] and ID#[3] to columns 0, 1, 2, and 3, respectively, by complementary data lines DL0#, DL1#, DL2#, and DL3#, respectively. Each row of CAM memory cells includes match logic (not shown) to indicate when a match condition occurs, i.e., when the data bit values stored in the CAM memory cells of that row match the applied data bit values ID[3:0]. For example, if the data bit values ID[0], ID[1], ID[2], and ID[3] are 0, 1, 0, and 0, respectively, the data bit values stored in the CAM cells along row 0 match the applied data bit values. Under these conditions, a match signal MS0 on match line ML0 is asserted TRUE. Because the applied data bit values do not match the data bit values stored in the CAM memory cells of rows 1 and 2, match signals MS1 and MS2 on match lines ML1 and ML2, respectively, are deasserted. Match signals MS0-MS2 can be used to determine any or all row addresses within CAM array 100 which have their match line asserted.
A CAM array does not always contain a match for a given input data value. However, some of the bits of a row may match the input data value, while other bits of the row do not match the input data value. In such cases, it is often desirable to locate the stored word that provides the xe2x80x9clongest matchxe2x80x9d with the input word. This xe2x80x9clongest matchxe2x80x9d determination involves selecting the row of CAM cells containing the longest string of data bit values providing a match with the data bit values of the input word, starting from either its least significant bit (LSB) or most significant bit (MSB).
FIG. 2 shows a block diagram of a conventional CAM system 200 providing longest match capability. CAM system 200 includes a bit-wise mask logic 210, a Mxc3x97N CAM array 220, a no-match decoder 230, a priority encoder 240 and software 250 for controlling the recursive mask generation process. Bit-wise mask logic 210 specifies a set of bits, or xe2x80x9csubfieldxe2x80x9d, from input data value ID[N-1:0] in response to a MASK signal received from software 250. The MASK signal is initially selected to cause only the shortest subfield of bits ID[N-1:0] to be transmitted through mask logic 210. This subfield of bits is transmitted to CAM array 220 as a key K, K#. CAM array 220 simultaneously compares key K, K# with all the stored words in its M rows of CAM cells, generating a match signal MS[M-1:0] made up of individual match signals MSM-1-MS0. If the applied data bit values specified by key K, K# match the corresponding stored data bit values in any row of CAM cells in CAM array 220, the corresponding match signal is asserted TRUE.
If at least one of the match signals MS[M-1:0] is asserted TRUE, no-match decoder 230 provides a logic FALSE NO_MATCH signal to software 250. In response, software 250 generates another MASK data word, which is selected to cause a wider subfield of bits ID[M-1:0] to be transmitted through mask logic 210. Note that software 250 must wait for no match decoder 230 to generate the NO_MATCH signal before generating the next MASK data word. Consequently, mask logic 210, 220, 230 and 240 is very much under-utilized, and the resultant throughput is low.
To perform a longest match operation, bit-wise mask logic 210 provides wider and wider subfields of input data value ID[N-1:0] until no match is detected with any row of CAM array 220. The subfields are widened by software 250, which progressively increases the number of enabling bits in the MASK data word. When no match is detected, no-match decoder 230 asserts a logic TRUE NO_MATCH signal, which causes priority encoder 240 to provide an address M_ADDR of the last match indicated by CAM array 220. If more than one match was indicated during the last pass, priority encoder 240 provides an address having the highest priority (e.g., the lowest address).
Although CAM system 200 is able to determine the longest match for a given input data value, the recursive comparison loops significantly increase the time required to perform the operation. In addition, the time required to obtain a result is non-deterministic (i.e., the result can be obtained after one recursive loop, two recursive loops, etc.). This can often have undesirable effects at the system level.
FIG. 3 shows a block diagram of another conventional CAM system 300 providing longest match capability. CAM system 300 includes mask logic blocks 310a, 310b, 310c, and 310d, an Mxc3x97N 3CAM array 320, no-match decoders 330a, 330b, 330c, and 330d, first-level priority encoders 340a, 340b, 340c, and 340d, and second-level priority encoder 350. Mask logic blocks 310a-310d receive an N-bit input data value ID[N-1:0] and specify keys Ka-Kd, respectively.
Keys Ka-Kd represent successively wider subsections of input data value ID[N-1:0], starting from either its LSB or MSB. Keys Ka, Kb, Kc, and Kd have widths A, B, C, and D, respectively, where 0 less than A less than B less than C less than Dxe2x89xa6N. Each key is compared to all of the words stored in CAM array 320. In response, CAM array 320 generates a set of match signals for each key. For example, CAM array 320 generates a first set of match signals MSa[M-1:0] in response to key Ka, and a second set of match signals MSb[M-1:0] in response to key Kb. Each set of match signals is provided to a corresponding first-level priority encoder and a corresponding no-match detector. For example, the first set of match signals MSa[M-1:0] is provided to first-level priority encoder 340a and no-match decoder 330a. 
If a match with key Ka is indicated by the first set of match signals MSa[M-1:0], first-level priority encoder 340a generates an address for the matching word having the highest priority (where the xe2x80x9chighest priorityxe2x80x9d is the lowest address having a matching word). If a no-match condition is detected, no-match decoder 330a asserts a logic TRUE signal. The outputs of first-level priority encoders 340a-340d and no-match decoders 330a-330d are coupled to second-level priority encoder 350, which provides the location of the word matching the widest key as address M_ADDR. For example, if no-match decoder 330c asserts a logic TRUE signal but no-match decoder 330b does not, second-level priority encoder 350 provides the address generated by first-level priority encoder 340b as longest match address M_ADDR.
Because CAM system 300 includes separate match logic for each key, it avoids the slow throughput resulting from multiple recursive passes associated with CAM system 200 (FIG. 2). However, CAM system 300 includes multiple mask logic blocks, multiple first-level priority encoders, multiple no-match decoders, and additional match logic (i.e., a second level priority encoder), which greatly increases hardware requirements of CAM system 300, increasing circuit size, complexity and cost.
It is therefore desirable to provide a CAM system that provides efficient longest match determination in a compact structure.
Accordingly, the present invention provides a CAM system including a CAM array and a splitter logic circuit. An input data value is divided into non-overlapping subfields by the splitter logic to form a series of keys. The keys can be any width. The first key of the series typically includes one or more bits from the least significant bit (LSB) side of the input data value, or one or more bits from the most significant bit (MSB) side of the input data value. The first key can be any width. The CAM array is divided along columns into a similar series of non-overlapping sub-arrays corresponding to the subfields defined by the series of keys. Therefore, the first CAM sub-array of the series typically contains either the LSB""s or MSB""s of all the words stored in the CAM array, as dictated by the configuration of the first key.
The first CAM sub-array simultaneously compares the first key with all its stored rows of data bit values to generate a first set of match signals. The first set of match signals disables each row of the second CAM sub-array for which the corresponding row of the first CAM sub-array did not show a match. During the next clock cycle, the second CAM sub-array simultaneously compares the second key to all of its enabled rows of stored data bit values to generate a second set of match signals. The second set of match signals disables each row of the third CAM sub-array for which the corresponding row of either the first or second CAM sub-array did not show a match. This comparison process is continued with all the keys in sequence.
Each successive comparison operation disables the match logic of more and more rows. The row of the CAM array that shows a match over the greatest number of comparison operations contains the longest match for the input data value. If multiple rows show a match over the same number of comparison operations, a priority encoder determines which location has priority.
Because the keys produced by the splitter logic are non-overlapping, a series of comparison operations can be pipelined to minimize the time required for the longest match. For example, if four keys are used, then four comparison operations must be performed to obtain the longest match for a first input data value. However, after this initial four-cycle latency period, a longest match can be provided for an additional input data value during each subsequent cycle.
At the same time, because each key is compared only to the corresponding subfields of the stored words, multiple copies of mask registers and match logic circuits are not required. This greatly simplifies the circuit design and reduces hardware costs compared with CAM system 300 shown in FIG. 3.
The widths of the keys can be set to provide as fine or coarse a comparison resolution as desired. By making each key a single bit, the most finest resolution comparison can be made between the input word and the stored words. By increasing the number of keys, the latency time required for the comparison process will be increased; however, the throughput of one longest match per cycle is maintained. Moreover, the key width can vary from key to key.